#include "config.h"

#include <math.h>

#include <clx/libECM.h>
#include <clx/ecm_list.h>

#include "blockcache.h"

#undef PARANOIA

#define LEAVE_PROB	0.9999
#define CSET_SIZE(cset)	(((cset)->bid_tail - (cset)->bid_head) + 1)
#define CRUN_SIZE(crun)	(((crun)->bid_tail - (crun)->bid_head) + 1)

#define IS_ADJACENT_CSETS(cset_prev, cset)	((cset_prev)->bid_tail + 1 == (cset)->bid_head)
#define IS_ADJACENT_CRUNS(crun_prev, crun)	((crun_prev)->bid_tail + 1 == (crun)->bid_head)
#define IS_ADJACENT_BIDS(bid1, bid2)	((bid1) + 1 == (bid2))

static LIST_HEAD(free_list);
static LIST_HEAD(csets);

static ecm_uint32	n_csets;
static ecm_uint32	n_cruns;

static ecm_hashtable_t	hash_session;

/* For simplicity, do not care performance */

typedef struct {
	ecm_uint32	mid;
	ecm_uint32	bid_max;
	struct list_head	csets;
} media_t;

typedef struct {
	bcache_t	*bcache;
	struct list_head	list;
} cblk_t;

typedef struct {
	media_t		*media;
	ecm_double	expection;
	ecm_double	myexpection;
	ecm_uint32	bid_head;
	ecm_uint32	bid_tail;
	ecm_uint32	n_sessions;
	ecm_uint32	iatime;
	struct list_head	sessions;
	/* for sorting */
	struct list_head	list;
	struct list_head	list_media;
	struct list_head	cruns;
} cset_t;

typedef struct {
	ecm_uint32	bid_head;
	ecm_uint32	bid_tail;
	struct list_head	cblks;
	struct list_head	list;
} crun_t;

typedef struct _session {
	ecm_uint32	sid;
	ecm_uint32	bid;
	cset_t		*cset;
	struct list_head	list;
} session_t;

static ecm_ptrs_t	*ptrs_media;

#ifdef PARANOIA

static void
show_media_cset_infos(media_t *media)
{
	cset_t	*cset;
	struct list_head	*lp;

	list_for_each (lp, &media->csets) {
		cset = list_entry(lp, cset_t, list_media);
		printf("%u:%u:%u[%.2lf] ", cset->bid_head, cset->bid_tail, cset->n_sessions, cset->bid_tail / cset->expection);
		{
			crun_t	*crun;
			cblk_t	*cblk;
			struct list_head *lq, *lt;
			
			list_for_each (lq, &cset->cruns) {
				crun = list_entry(lq, crun_t, list);
				list_for_each (lt, &crun->cblks) {
					cblk = list_entry(lt, cblk_t, list);
					printf("%u ", cblk->bcache->bid);///TEST
				}
			}
		}
	}
	printf("\n");
}

static void
check_crun_sanity(crun_t *crun)
{
	cblk_t	*cblk;
	ecm_uint32	bid, bid_prev = 0;
	struct list_head	*lp;

	ECMASSERT(crun->bid_head <= crun->bid_tail);
	list_for_each (lp, &crun->cblks) {
		cblk = list_entry(lp, cblk_t, list);
		bid = cblk->bcache->bid;
		ECMASSERT(bid >= crun->bid_head && bid <= crun->bid_tail);
		if (bid_prev != 0)
			ECMASSERT(bid > bid_prev);
		bid_prev = bid;
	}
}

static void
check_expection(cset_t *cset)
{
	cset_t	*cset_list;
	struct list_head	*lp;
	ecm_double	expection = 0;
	ecm_double	myexpection;

	list_for_each (lp, &cset->media->csets) {
		cset_list = list_entry(lp, cset_t, list_media);

		expection += (pow(LEAVE_PROB, cset->bid_tail - cset_list->bid_head) * cset_list->n_sessions);
		if (cset_list == cset)
			break;
	}
	///TODO
	if (cset->iatime > 0)
		expection += pow(LEAVE_PROB, cset->iatime + (cset->bid_tail - 1));

	ECMASSERT(fabs(expection - cset->expection) < 0.01);
	myexpection = pow(LEAVE_PROB, cset->bid_tail - cset->bid_head) * cset->n_sessions;
	ECMASSERT(fabs(cset->myexpection - myexpection) < 0.001);
}

static void
check_cset_sanity(cset_t *cset)
{
	crun_t	*crun, *crun_prev = NULL;
	struct list_head	*lp;

	ECMASSERT(cset->n_sessions == 0 || cset->expection != 0);

	list_for_each (lp, &cset->cruns) {
		crun = list_entry(lp, crun_t, list);
		ECMASSERT(crun->bid_head >= cset->bid_head && crun->bid_tail <= cset->bid_tail);
		check_crun_sanity(crun);
		if (crun_prev != NULL) {
			ECMASSERT(crun->bid_head > crun_prev->bid_tail);
			ECMASSERT(!IS_ADJACENT_CRUNS(crun_prev, crun));
		}
		crun_prev = crun;
	}
}

static void
check_all_cset_expection_sanity(void)
{
	media_t	*media;
	cset_t	*cset;
	struct list_head	*lp;
	int	i;

	for (i = 0; i < ptrs_media->len; i++) {
		media = (media_t *)ptrs_media->pdata[i];
		list_for_each (lp, &media->csets) {
			cset = list_entry(lp, cset_t, list_media);
			check_cset_sanity(cset);
			check_expection(cset);
		}
	}
}

static void
check_cset_sorting_sanity(void)
{
	ecm_double      x = 1000000000;
	ecm_double      y;

	list_for_each (lp, &csets) {
		cset = list_entry(lp, cset_t, list);
		if (cset->expection > 0) {
			y = (cset->iatime + cset->bid_tail) / cset->expection;
			ECMASSERT(x >= y);
			x = y;
		}
	}
}

static void
check_all_cset_sanity(void)
{
#if 0 ////TEST
	show_media_cset_infos(ptrs_media->pdata[0]);
#endif

	check_all_cset_expection_sanity();
	check_cset_sorting_sanity();
}

#define CHECK_CRUN_SANITY(crun)	check_crun_sanity(crun)
#define CHECK_CSET_SANITY(cset)	check_cset_sanity(cset)
#define CHECK_ALL_CSET_SANITY()	check_all_cset_sanity()

#else

#define CHECK_CRUN_SANITY(crun)	do {} while (0)
#define CHECK_CSET_SANITY(cset)	do {} while (0)
#define CHECK_ALL_CSET_SANITY(cset)	do {} while (0)

#endif

static void
collect_cache(cset_t *cset)
{
	///TODO
}

static cset_t *
create_cset(media_t *media, ecm_uint32 bid)
{
	cset_t	*cset;

	cset = (cset_t *)ecm_malloc(sizeof(cset_t));
	ECMASSERT(cset != NULL);

	cset->media = media;
	cset->expection = 0.0;
	cset->myexpection = 0.0;
	cset->bid_head = bid;
	cset->bid_tail = bid;
	cset->n_sessions = 0;
	cset->iatime = 0;
	INIT_LIST_HEAD(&cset->sessions);

	INIT_LIST_HEAD(&cset->list);
	INIT_LIST_HEAD(&cset->list_media);
	INIT_LIST_HEAD(&cset->cruns);

	n_csets++;

	return cset;
}

static void
free_cset(cset_t *cset)
{
	list_del(&cset->list);
	list_del(&cset->list_media);
	ecm_free(cset);

	ECMASSERT(n_csets > 0);
	n_csets--;
}

static crun_t *
create_crun(ecm_uint32 bid_head, ecm_uint32 bid_tail)
{
	crun_t	*crun;

	ECMASSERT(bid_head <= bid_tail);

	crun = (crun_t *)ecm_malloc(sizeof(crun_t));
	ECMASSERT(crun != NULL);

	crun->bid_head = bid_head;
	crun->bid_tail = bid_tail;
	INIT_LIST_HEAD(&crun->cblks);
	INIT_LIST_HEAD(&crun->list);

	n_cruns++;
	return crun;
}

static void
free_crun(crun_t *crun)
{
	list_del(&crun->list);
	ecm_free(crun);

	ECMASSERT(n_cruns > 0);
	n_cruns--;
}

/**
 * sort cset again
 */
///TODO sorting value should be devised instead of each-time calculation.
static void
sort_cset(cset_t *cset, ECMBOOL forward)
{
	struct list_head	*lp, *first;
	ecm_double	expection;
	cset_t	*cset_list;

	ECMASSERT(!list_empty(&cset->list));

	first = (forward) ? cset->list.next : cset->list.prev;
	list_del(&cset->list);

	expection = (cset->iatime + cset->bid_tail) / cset->expection;

	if (forward) {
		for (lp = first; lp != &csets; lp = lp->next) {
			cset_list = list_entry(lp, cset_t, list);
			if (expection > (cset_list->iatime + cset_list->bid_tail) / cset_list->expection) {
				list_add_tail(&cset->list, &cset_list->list);
				return;
			}
		}
		list_add_tail(&cset->list, &csets);
	}
	else {
		for (lp = first; lp != &csets; lp = lp->prev) {
			cset_list = list_entry(lp, cset_t, list);
			if (expection < (cset_list->iatime + cset_list->bid_tail) / cset_list->expection) {
				list_add(&cset->list, &cset_list->list);
				return;
			}
		}
		list_add(&cset->list, &csets);
	}
}

static ecm_double
calc_expection(cset_t *cset, cset_t *cset_ref)
{
	return pow(LEAVE_PROB, cset->bid_tail - cset_ref->bid_head);
}

static ecm_double
calc_upward_expection_diff(cset_t *cset, cset_t *cset_ref)
{
	if (cset->bid_tail == cset_ref->bid_head)
		return 0;

	return pow(LEAVE_PROB, cset->bid_tail - (cset_ref->bid_head + 1))
		- pow(LEAVE_PROB, cset->bid_tail - cset_ref->bid_head);
}

static void
set_cset_bid_tail(cset_t *cset, ecm_uint32 bid_tail)
{
	ecm_uint32	bid_tail_old;

	if (bid_tail == cset->bid_tail)
		return;

	ECMASSERT(cset->bid_head <= bid_tail);

	bid_tail_old = cset->bid_tail;
	cset->bid_tail = bid_tail;

	if (bid_tail_old > bid_tail) {
		/* shrink crun */
		ecm_double	coeff = pow(LEAVE_PROB, bid_tail_old - bid_tail);

		cset->expection /= coeff;
		cset->myexpection /= coeff;
		sort_cset(cset, ECM_TRUE);
	}
	else {
		/* expand crun */
		ecm_double	coeff = pow(LEAVE_PROB, bid_tail - bid_tail_old);

		cset->expection *= coeff;
		cset->myexpection *= coeff;
		sort_cset(cset, ECM_FALSE);
	}
}

/**
 * @brief shrink crun after losing the cblk of a tail.
 */
static void
shrink_crun(cset_t *cset, crun_t *crun)
{
	ecm_uint32	bid_tail;

	if (list_empty(&crun->cblks)) {
		free_crun(crun);
	}
	else {
		cblk_t	*cblk_tail;

		cblk_tail = list_entry(crun->cblks.prev, cblk_t, list);
		crun->bid_tail = cblk_tail->bcache->bid;
	}

	/* check cset */
	if (list_empty(&cset->cruns)) {
		if (cset->n_sessions == 0) {
			free_cset(cset);
			return;
		}
		bid_tail = cset->bid_head;
	}
	else {
		crun_t	*crun_tail;

		crun_tail = list_entry(cset->cruns.prev, crun_t, list);
		ECMASSERT(crun_tail->bid_tail <= cset->bid_tail);
		if (crun_tail->bid_tail == cset->bid_tail)
			return;
		bid_tail = crun_tail->bid_tail;
	}

	set_cset_bid_tail(cset, bid_tail);
}

static void
raise_expection(cset_t *cset)
{
	cset_t	*cset_list;
	struct list_head	*lp = &cset->list_media;
	struct list_head	*head = &cset->media->csets;
	ecm_double	curexp;

	curexp = calc_expection(cset, cset);
	cset->myexpection += curexp;
	cset->expection += curexp;
	sort_cset(cset, ECM_TRUE);

	for (lp = cset->list_media.next; lp != head; lp = lp->next) {
		cset_list = list_entry(lp, cset_t, list_media);
		cset_list->expection += calc_expection(cset_list, cset);
		sort_cset(cset_list, ECM_TRUE);
	}
}

/**
 * @brief drop the expection of cset by session leaving.
 */
static void
drop_expection(cset_t *cset)
{
	cset_t	*cset_list;
	struct list_head	*lp;
	struct list_head	*head = &cset->media->csets;

	if (cset->n_sessions == 0) {
		cset->expection -= cset->myexpection;
		cset->myexpection = 0;
	}
	else {
		ecm_double	curexp;
		curexp = cset->myexpection / cset->n_sessions;
		cset->expection -= curexp;
		cset->myexpection -= curexp;
	}
	sort_cset(cset, ECM_FALSE);

	for (lp = cset->list_media.next; lp != head; lp = lp->next) {
		cset_list = list_entry(lp, cset_t, list_media);
		cset_list->expection -= calc_expection(cset_list, cset);
		if (cset_list->expection < 0)
			cset_list->expection = 0;
		sort_cset(cset_list, ECM_FALSE);
	}
}

static ecm_double
get_initial_expection(cset_t *cset, ecm_uint32 bid)
{
	media_t	*media = cset->media;
	ecm_uint32	iablks;

	iablks = bc_get_inter_arrival_blks(media->mid);
	if (iablks == 0)
		return 0.0;
	cset->iatime = iablks;
	return pow(LEAVE_PROB, iablks + (bid -1));
}

/**
 * @brief init expection
 */
static void
init_expection(cset_t *cset)
{
	media_t	*media = cset->media;
	cset_t	*cset_list;
	struct list_head	*lp;

	cset->expection = get_initial_expection(cset, cset->bid_tail);

	for (lp = media->csets.next; lp != &cset->list_media; lp = lp->next) {
		cset_list = list_entry(lp, cset_t, list_media);

		if (cset_list->n_sessions > 0)
			cset->expection += (calc_expection(cset, cset_list) * cset_list->n_sessions);
	}
}

/**
 * @brief upward expection
 */
static void
upward_expection(cset_t *cset)
{
	cset_t	*cset_list;
	struct list_head	*lp;
	struct list_head	*head = &cset->media->csets;

	ECMASSERT(cset->n_sessions == 1);

	if (CSET_SIZE(cset) > 1) {
		cset->expection -= cset->myexpection;
		cset->myexpection /= LEAVE_PROB;
		cset->expection += cset->myexpection;
		sort_cset(cset, ECM_TRUE);
	}
	else {
		cset->expection -= cset->myexpection;
		cset->expection *= LEAVE_PROB;
		cset->expection += cset->myexpection;
		sort_cset(cset, ECM_FALSE);
	}

	for (lp = cset->list_media.next; lp != head; lp = lp->next) {
		cset_list = list_entry(lp, cset_t, list_media);
		cset_list->expection += calc_upward_expection_diff(cset_list, cset);
		sort_cset(cset_list, ECM_TRUE);
	}
}

static cset_t *
build_cset(ecm_uint32 bid, media_t *media, cset_t *cset_prev, cset_t *cset_next)
{
	cset_t	*cset;

	ECMASSERT(cset_prev == NULL || cset_next == NULL);
	ECMASSERT(cset_prev == NULL || bid > cset_prev->bid_tail);
	ECMASSERT(cset_next == NULL || bid < cset_next->bid_head);

	cset = create_cset(media, bid);
	if (cset_prev == NULL && cset_next == NULL) {
		list_add(&cset->list_media, &media->csets);
	}
	else if (cset_prev != NULL) {
		list_add(&cset->list_media, &cset_prev->list_media);
	}
	else {
		list_add_tail(&cset->list_media, &cset_next->list_media);
	}

	list_add(&cset->list, &csets);
	init_expection(cset);
	sort_cset(cset, ECM_TRUE);

	collect_cache(cset);

	return cset;
}

/* Matched crun not found.
 * But any adjacent crun should be checked before new crun will be created
 */
static crun_t *
build_crun(cset_t *cset, ecm_uint32 bid, crun_t *crun_prev, crun_t *crun_next)
{
	crun_t	*crun;

	ECMASSERT(crun_prev == NULL || crun_next == NULL);
	ECMASSERT(crun_prev == NULL || bid > crun_prev->bid_tail);
	ECMASSERT(crun_next == NULL || bid < crun_next->bid_tail);
	ECMASSERT(bid >= cset->bid_head);

	if (crun_prev == NULL && crun_next == NULL) {
		crun = create_crun(bid, bid);

		ECMASSERT(list_empty(&cset->cruns));
		list_add(&crun->list, &cset->cruns);
	}
	else if (crun_prev != NULL) {
		/* If a adjacent previous crun is found, just increase that crun size instead of creating new one */
		if (IS_ADJACENT_BIDS(crun_prev->bid_tail, bid)) {
			crun_prev->bid_tail++;
			crun = crun_prev;
		}
		else {
			crun = create_crun(bid, bid);
			list_add(&crun->list, &crun_prev->list);
		}
	}
	else {
		crun = create_crun(bid, bid);
		list_add_tail(&crun->list, &crun_next->list);
	}

	if (crun->bid_tail > cset->bid_tail)
		set_cset_bid_tail(cset, crun->bid_tail);

	return crun;
}

static crun_t *
build_splitted_crun(cset_t *cset, ecm_uint32 bid_head, ecm_uint32 bid_tail, crun_t *crun_prev)
{
	crun_t	*crun;

	crun = create_crun(bid_head, bid_tail);
	list_add(&crun->list, &crun_prev->list);

	return crun;
}

static cset_t *
find_cset_forward(struct list_head *head, struct list_head *lp, ecm_uint32 bid, media_t *media)
{
	cset_t	*cset;

	for (; lp != &media->csets; lp = lp->next) {
		cset = list_entry(lp, cset_t, list_media);
		ECMASSERT(cset->bid_head <= cset->bid_tail);

		if (bid < cset->bid_head)
			return build_cset(bid, media, NULL, cset);
		if (bid >= cset->bid_head && bid <= cset->bid_tail)
			return cset;
	}

	cset = list_entry(media->csets.prev, cset_t, list_media);
	return build_cset(bid, media, cset, NULL);
}

static cset_t *
find_cset_backward(struct list_head *head, struct list_head *lp, ecm_uint32 bid, media_t *media)
{
	cset_t	*cset;

	for (; lp != &media->csets; lp = lp->prev) {
		cset = list_entry(lp, cset_t, list_media);
		ECMASSERT(cset->bid_head <= cset->bid_tail);

		if (bid > cset->bid_tail)
			return build_cset(bid, media, cset, NULL);
		if (bid >= cset->bid_head && bid <= cset->bid_tail)
			return cset;
	}

	cset = list_entry(media->csets.next, cset_t, list_media);
	return build_cset(bid, media, NULL, cset);
}

/**
 * @brief find the included cset. If not found, create cset.
 *
 */
static cset_t *
find_cset(media_t *media, ecm_uint32 bid, cset_t *cset)
{
	ECMASSERT(media != NULL && bid > 0);

	if (list_empty(&media->csets)) {
		return build_cset(bid, media, NULL, NULL);
	}

	if (cset == NULL) {
		/* no hint cset provided. Just search at first position. */
		return find_cset_forward(&media->csets, media->csets.next, bid, media);
	}

	if (bid < cset->bid_head) {
		if (cset->list_media.prev == &media->csets)
			return build_cset(bid, media, NULL, cset);
		return find_cset_backward(&media->csets, cset->list_media.prev, bid, media);
	}
	if (bid > cset->bid_tail) {
		if (cset->list_media.next == &media->csets)
			return build_cset(bid, media, cset, NULL);
		return find_cset_forward(&media->csets, cset->list_media.next, bid, media);
	}

	return cset;
}

/**
 * @brief Find the matching crun which can be created if not found.
 * As a result, cset can be extended.
 *
 */
static crun_t *
find_crun(cset_t *cset, ecm_uint32 bid)
{
	crun_t	*crun;
	struct list_head	*lp;

	if (list_empty(&cset->cruns)) {
		return build_crun(cset, bid, NULL, NULL);
	}

	/* Do backward search from highest crun */
	for (lp = cset->cruns.prev; lp != &cset->cruns; lp = lp->prev) {
		crun = list_entry(lp, crun_t, list);
		if (bid > crun->bid_tail) {
			return build_crun(cset, bid, crun, NULL);
		}
		if (bid >= crun->bid_head && bid <= crun->bid_tail)
			return crun;
	}

	return build_crun(cset, bid, NULL, crun);
}

/**
 * @brief session is unaccessing cset
 */
static void
unaccess_cset(session_t *session)
{
	cset_t	*cset = session->cset;

	ECMASSERT(!list_empty(&session->list) && cset != NULL);

	drop_expection(cset);

	list_del_init(&session->list);
	session->cset = NULL;
	ECMASSERT(cset->n_sessions > 0);
	cset->n_sessions--;
}

static void
access_cset(session_t *session, cset_t *cset)
{
	ECMASSERT(list_empty(&session->list) && session->cset == NULL);

	list_add_tail(&session->list, &cset->sessions);
	session->cset = cset;
	cset->n_sessions++;

	raise_expection(cset);
}

static void
split_crun_cblks(crun_t *crun, crun_t *crun_new)
{
	ecm_uint32	bid = crun_new->bid_head;
	cblk_t	*cblk;
	struct list_head	*lp;

	list_for_each (lp, &crun->cblks) {
		cblk = list_entry(lp, cblk_t, list);

		if (bid <= cblk->bcache->bid)
			break;
	}
	if (lp != &crun->cblks) {
		ECMASSERT(list_empty(&crun_new->cblks));

		crun_new->cblks.next = lp;
		crun_new->cblks.prev = crun->cblks.prev;
		lp->prev->next = &crun->cblks;
		crun->cblks.prev->next = &crun_new->cblks;
		crun->cblks.prev = lp->prev;
		lp->prev = &crun_new->cblks;
	}
}

static void
split_crun(cset_t *cset, crun_t *crun, ecm_uint32 bid)
{
	crun_t	*crun_new;
	ecm_uint32	bid_tail;

	ECMASSERT(crun->bid_head < bid && bid <= crun->bid_tail);

	bid_tail = crun->bid_tail;
	crun->bid_tail = bid - 1;

	crun_new = build_splitted_crun(cset, bid, bid_tail, crun);

	split_crun_cblks(crun, crun_new);
}

/**
 * @brief get cache blocks from splitted cset
 */
static void
split_cset_cruns(cset_t *cset, cset_t *cset_new)
{
	ecm_uint32	bid = cset_new->bid_head;
	crun_t	*crun;
	struct list_head	*lp;

	list_for_each (lp, &cset->cruns) {
		crun = list_entry(lp, crun_t, list);

		CHECK_CRUN_SANITY(crun);

		if (bid <= crun->bid_head)
			break;
		if (bid > crun->bid_head && bid <= crun->bid_tail) {
			split_crun(cset, crun, bid);
			lp = lp->next;
			break;
		}
	}
	if (lp != &cset->cruns) {
		ECMASSERT(list_empty(&cset_new->cruns));

		cset_new->cruns.next = lp;
		cset_new->cruns.prev = cset->cruns.prev;
		lp->prev->next = &cset->cruns;
		cset->cruns.prev->next = &cset_new->cruns;
		cset->cruns.prev = lp->prev;
		lp->prev = &cset_new->cruns;
	}
}

/**
 * @brief cache run splitted by newly positioned session
 */
static void
split_cset(cset_t *cset, session_t *session)
{
	cset_t	*cset_new;
	ecm_uint32	bid_tail;

	ECMASSERT(session->cset == NULL);
	ECMASSERT(cset->bid_head <= session->bid && session->bid <= cset->bid_tail);

	bid_tail = cset->bid_tail;
	set_cset_bid_tail(cset, session->bid - 1);

	cset_new = build_cset(session->bid, cset->media, cset, NULL);
	set_cset_bid_tail(cset_new, bid_tail);

	split_cset_cruns(cset, cset_new);

	access_cset(session, cset_new);
}

static void
merge_crun_cblks(crun_t *crun, crun_t *crun_prev)
{
	list_splice(&crun->cblks, crun_prev->cblks.prev);
	crun_prev->bid_tail = crun->bid_tail;
}

static void
merge_cset_cruns(cset_t *cset, cset_t *cset_prev)
{
	crun_t	*crun;

	if (list_empty(&cset->cruns))
		crun = NULL;
	else
		crun = list_entry(cset->cruns.next, crun_t, list);

	list_splice(&cset->cruns, cset_prev->cruns.prev);
	INIT_LIST_HEAD(&cset->cruns);

	if (crun != NULL && crun->list.prev != &cset_prev->cruns) {
		crun_t	*crun_prev = list_entry(crun->list.prev, crun_t, list);

		if (IS_ADJACENT_CRUNS(crun_prev, crun)) {
			merge_crun_cblks(crun, crun_prev);
			free_crun(crun);
		}
	}
	set_cset_bid_tail(cset_prev, cset->bid_tail);
}

/**
 * @brief get victim cblk from cset
 */
static cblk_t *
get_victim_cblk(cset_t *cset)
{
	cblk_t	*cblk;
	struct list_head	*lp;

	if (list_empty(&cset->cruns))
		return NULL;

	for (lp = cset->cruns.prev; lp != &cset->cruns; lp = lp->prev) {
		crun_t	*crun = list_entry(lp, crun_t, list);

		ECMASSERT(crun->bid_head >= cset->bid_head);
		ECMASSERT(crun->bid_tail <= cset->bid_tail);

		if (list_empty(&crun->cblks))
			continue;
	
		cblk = list_entry(crun->cblks.prev, cblk_t, list);

		ECMASSERT(crun->bid_head <= cblk->bcache->bid);
		ECMASSERT(crun->bid_tail >= cblk->bcache->bid);

		list_del_init(&cblk->list);

		shrink_crun(cset, crun);

		return cblk;
	}
	return NULL;
}

/**
 * @brief Insert newly or cut-out session to form a cset.
 */
static void
putdown_session(session_t *session, cset_t *cset)
{
	ECMASSERT(list_empty(&session->list) && session->cset == NULL);
	ECMASSERT(session->bid >= cset->bid_head || session->bid <= cset->bid_tail);
	
	if (session->bid == cset->bid_head)
		access_cset(session, cset);
	else
		split_cset(cset, session);
}

static session_t *
create_session(ecm_uint32 sid)
{
	session_t	*session;

	session = (session_t *)ecm_malloc(sizeof(session_t));
	session->sid = sid;
	session->bid = 0;
	session->cset = NULL;
	INIT_LIST_HEAD(&session->list);

	ecm_hashtable_insert(hash_session, session, sizeof(sid), &sid);

	return session;
}

static void
free_session(session_t *session)
{
	ecm_hashtable_remove(hash_session, sizeof(ecm_uint32), &session->sid);
	ecm_free(session);
}

static session_t *
get_session(ecm_uint32 sid)
{
	session_t	*session;

	session = (session_t *)ecm_hashtable_get(hash_session, sizeof(sid), &sid);
	if (session == NULL)
		return create_session(sid);
	return session;
}

static media_t *
get_media(ecm_uint32 mid)
{
	media_t	*media;

	media = (media_t *)ecm_ptrs_get(ptrs_media, mid);
	ECMASSERT(media != NULL);

	return media;
}

static void
merge_crun_next(cset_t *cset, crun_t *crun)
{
	crun_t	*crun_next;

	if (crun->list.next == &cset->cruns)
		return;
	crun_next = list_entry(crun->list.next, crun_t, list);
	if (IS_ADJACENT_CRUNS(crun, crun_next)) {
		merge_crun_cblks(crun_next, crun);
		free_crun(crun_next);
	}
}

/**
 * @brief Insert cblk into cset. cset can be extended to hold cblk
 */
static void
insert_cblk(cset_t *cset, cblk_t *cblk)
{
	crun_t	*crun;
	cblk_t	*cblk_list;
	ecm_uint32	bid = cblk->bcache->bid;
	struct list_head	*lp;

	ECMASSERT(list_empty(&cblk->list));
	ECMASSERT(cset->bid_head <= bid);

	crun = find_crun(cset, bid);
	ECMASSERT(crun != NULL);

	for (lp = crun->cblks.prev; lp != &crun->cblks; lp = lp->prev) {
		cblk_list = list_entry(lp, cblk_t, list);

		ECMASSERT(cblk_list->bcache->mid == cblk->bcache->mid);
		ECMASSERT(cblk_list->bcache->bid != cblk->bcache->bid);

		if (cblk->bcache->bid > cblk_list->bcache->bid) {
			list_add(&cblk->list, &cblk_list->list);
			CHECK_CRUN_SANITY(crun);
			return;
		}
	}
	list_add(&cblk->list, &crun->cblks);

	/* Check we can merge next crun */
	merge_crun_next(cset, crun);

	CHECK_CRUN_SANITY(crun);
}

static const char *
lef_init(ecm_uint32 cache_blksize, ecm_uint32 n_caches)
{
	ptrs_media = ecm_ptrs_new(16);

	hash_session = ecm_hashtable_create(32);

	return "LEF";
}

static void
lef_create(bcache_t *bcache)
{
	cblk_t	*cblk;

	cblk = (cblk_t *)ecm_malloc(sizeof(cblk_t));
	bcache->priv = cblk;
	cblk->bcache = bcache;
	list_add(&cblk->list, &free_list);
}

static void
lef_hit(bcache_t *bcache)
{
	cblk_t	*cblk = (cblk_t *)bcache->priv;

	list_del_init(&cblk->list);
}

static bcache_t *
lef_replace(ecm_uint32 mid, ecm_uint32 bid)
{
	cblk_t	*cblk;
	cset_t	*cset;
	struct list_head	*lp;

	if (!list_empty(&free_list)) {
		cblk = list_entry(free_list.next, cblk_t, list);
		list_del_init(&cblk->list);
		return cblk->bcache;
	}

	list_for_each (lp, &csets) {
		cset = list_entry(lp, cset_t, list);
		if ((cblk = get_victim_cblk(cset)) == NULL)
			continue;
		return cblk->bcache;
	}
	return NULL;
}

static cset_t *
get_next_cset(cset_t *cset)
{
	media_t	*media = cset->media;

	if (cset->list_media.next != &media->csets) {
		cset_t	*cset_next;

		cset_next = list_entry(cset->list_media.next, cset_t, list_media);
		if (cset->bid_tail == cset_next->bid_head - 1)
			return cset_next;
	}

	return NULL;
}

/**
 * @brief get previous cset
 */
static cset_t *
get_prev_cset(cset_t *cset)
{
	media_t	*media = cset->media;

	if (cset->list_media.prev != &media->csets)
		return list_entry(cset->list_media.prev, cset_t, list_media);

	return NULL;
}

static void
merge_cset(cset_t *cset)
{
	cset_t	*cset_prev;

	/* check if cset is needed to be merged with previous cset */
	cset_prev = get_prev_cset(cset);
	if (cset_prev == NULL)
		return;

	ECMASSERT(cset_prev->bid_tail < cset->bid_head);
	if (!IS_ADJACENT_CSETS(cset_prev, cset)) {
		/* We can only merge two adjacent csets */
		return;
	}

	/* merge cruns */
	merge_cset_cruns(cset, cset_prev);

	free_cset(cset);
}

/**
 * @brief cut out session. It may cause csets to be merged or deleted.
 */
static void
cut_session(session_t *session)
{
	cset_t	*cset;

	cset = session->cset;
	unaccess_cset(session);

	if (!list_empty(&cset->sessions))
		return;

	merge_cset(cset);
}

static void
advance_crun_head(cset_t *cset, crun_t *crun)
{
	if (CRUN_SIZE(crun) == 1) {
		if (crun->list.next != &cset->cruns) {
			crun_t	*crun_next = list_entry(crun->list.next, crun_t, list);
			if (crun_next->bid_head == crun->bid_tail + 2) {
				crun_next->bid_head--;
				free_crun(crun);
				return;
			}
		}
		crun->bid_head++;
		crun->bid_tail++;
	}
	else {
		crun->bid_head++;
	}
}

/**
 * @brief Increase one bid due to sequential access
 */
static void
advance_cset(cset_t *cset)
{
	crun_t	*crun = NULL;
	cblk_t	*cblk = NULL;

	/* get cblk to be handovered to previous cset if any */
	if (!list_empty(&cset->cruns)) {
		crun = list_entry(cset->cruns.next, crun_t, list);
		if (crun->bid_head == cset->bid_head) {
			if (!list_empty(&crun->cblks)) {
				cblk = list_entry(crun->cblks.next, cblk_t, list);

				if (cblk->bcache->bid == crun->bid_head)
					list_del_init(&cblk->list);
				else
					cblk = NULL;
			}
			advance_crun_head(cset, crun);
		}
	}

	if (CSET_SIZE(cset) == 1) {
		cset->bid_head++;
		cset->bid_tail++;
	}
	else {
		cset->bid_head++;
	}
	
	upward_expection(cset);

	if (cblk != NULL) {
		cset_t	*cset_prev;

		cset_prev = get_prev_cset(cset);
		if (cset_prev == NULL)
			cset_prev = build_cset(cset->bid_head - 1, cset->media, NULL, cset);

		insert_cblk(cset_prev, cblk);
	}
}

static void
lef_seq_access(session_t *session)
{
	cset_t	*cset, *cset_next;
	ecm_uint32	bid = session->bid;

	cset = session->cset;

	ECMASSERT(IS_ADJACENT_BIDS(cset->bid_head, bid));

	cset_next = get_next_cset(cset);

	if (CSET_SIZE(cset) == 1) {
		cset_t	*cset_prev;

		cset_prev = get_prev_cset(cset);
		if (cset_next == NULL && (cset_prev == NULL || cset->n_sessions > 1))
			cset_next = build_cset(bid, cset->media, cset, NULL);

		if (cset_next) {
			unaccess_cset(session);
			access_cset(session, cset_next);
			if (cset->n_sessions == 0)
				merge_cset(cset);
		}
		else {
			ECMASSERT(cset_prev != NULL && cset->n_sessions == 1);

			advance_cset(cset);
		}
	}
	else {
		if (cset->n_sessions == 1) {
			advance_cset(cset);
		}
		else {
			/* cset used by multiple sessions. */
			unaccess_cset(session);
			split_cset(cset, session);
		}
	}
}

static void
lef_1st_access(session_t *session, media_t *media)
{
	cset_t	*cset;

	ECMASSERT(session->cset == NULL);

	cset = find_cset(media, session->bid, NULL);
	putdown_session(session, cset);
}

static void
lef_access(ecm_uint32 sid, ecm_uint32 mid, ecm_uint32 bid)
{
}

static void
lef_put(ecm_uint32 sid, bcache_t *bcache)
{
	session_t	*session;
	ecm_uint32	mid, bid;
	cblk_t		*cblk = (cblk_t *)bcache->priv;
	cset_t		*cset;

	mid = bcache->mid;
	bid = bcache->bid;

	session = get_session(sid);
	ECMASSERT(session != NULL);

	if (session->bid == 0) {
		session->bid = bid;
		lef_1st_access(session, get_media(mid));
	}
	else {
		cset = session->cset;
		CHECK_CSET_SANITY(cset);
		ECMASSERT(cset != NULL && cset->bid_head == session->bid);

		if (bid != cset->bid_head) {
			if (IS_ADJACENT_BIDS(cset->bid_head, bid)) {
				/* sequential access */
				session->bid = bid;
				lef_seq_access(session);
			}
			else {
				media_t	*media = cset->media;

				cut_session(session);
				cset = find_cset(media, bid, NULL);
				session->bid = bid;
				putdown_session(session, cset);
			}
		}
	}

	cset = session->cset;
	ECMASSERT(cset != NULL);
	insert_cblk(cset, cblk);

	CHECK_ALL_CSET_SANITY();
}

static void
lef_leave(ecm_uint32 sid)
{
	session_t	*session;

	session = (session_t *)ecm_hashtable_get(hash_session, sizeof(sid), &sid);
	if (session == NULL)
		return;

	cut_session(session);
	free_session(session);
}

static void
lef_add_media(ecm_uint32 bid_max)
{
	media_t		*media;

	media = (media_t *)ecm_malloc(sizeof(media_t));
	media->mid = ptrs_media->count + 1;
	media->bid_max = bid_max;
	INIT_LIST_HEAD(&media->csets);
	ecm_ptrs_add(ptrs_media, media);
}

static void
lef_fini(void)
{
	show_media_cset_infos(ptrs_media->pdata[0]);///TEST
}

blockcache_op_t	bcache_op = {
	lef_init,
	NULL,
	NULL,
	lef_add_media,

	lef_create,
	lef_hit,
	lef_replace,
	lef_put,

	lef_access,
	lef_leave,
	lef_fini
};
